/*
 * Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") > false
isMatch("aa","aa") > true
isMatch("aaa","aa") > false
isMatch("aa", "*") > true
isMatch("aa", "a*") > true
isMatch("ab", "?*") > true
isMatch("aab", "c*a*b") > false
 */
package com.xinpan.exercise;

public class WildcardMatching {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(p.length() == 0)
            return (s.length() == 0);
        
        if(p.charAt(0) == '*')
        {
            for(int i = s.length(); i >= 0; i--)
                if(isMatch(s.substring(i, s.length()), p.substring(1, p.length())))
                    return true;
            return false;
        }
        else if(p.charAt(0) == '?')
            return (s.length() > 0 &&  
                isMatch(s.substring(1, s.length()), p.substring(1, p.length())));
        else
            return (s.length() > 0 &&
                    p.charAt(0) == s.charAt(0) &&
                    isMatch(s.substring(1, s.length()), p.substring(1, p.length())));
    }
    
    public static void main(String[] args)
    {
    	WildcardMatching wm = new WildcardMatching();
    	wm.isMatch("aa", "a*");
    }
}
